Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

\[ \newcommand{\IR}{\mathbb{R}} \newcommand{\coloneqq}{:=} \]

Computational Game Theory


Lecture:

Tue, 14:15-15:45 in JUR, SR 154
Wed, 10:15-11:45 in JUR, SR 154

by Lukas Graf
lukas.graf@uni-passau.de

Exercise:

Thu, 16:00-17:30 in IM, HS 12


by Julian Schwarz
julian.schwarz@uni-passau.de

Oral Exam:
~ July 24th
start with 5 min talk (optional)

Game Theory


study of games

e.g. NIM:
Rules:
  • Every turn: Remove 1-5 coins
  • Winner: Player who removes last coin

study of game-like situations

e.g. exam-preparations
Lecture Overview
  1. Strategic Games
  2. Computation of Mixed Nash Equilibria
  3. Potential Games
  4. Congestion Games
  5. Pricing in Ressource Allocation Games
  6. Combinatorial Auctions
  7. Cooperative Game Theory

Recap

strategic game $G=(N,S,u)$:
  • $N = \{1,\dots,n\}$ set of players
  • $S_i$ strategies of player $i \in N$
  • $u_i: S \to \IR$ utility fct. of player $i$

$s^* \in S$ (pure) Nash equilibrium (PNE) if
  $u_i(s^*) \geq u_i(s_i,s^*_{-i})$ f.a. $s_i \in S_i, i \in N$.
  $\iff s^* \in B(s^*) \coloneqq \prod_i B_i(s^*_{-i})$, where $B_i(s^*_{-i})$ is the set of best responses (for player $i$)

$G=(N,S,u)$ zero sum game if
  • $N = [2]$
  • $u_1 = -u_2$

Thm. 1.16: In finite zero-sum the following are equivalent:
  1. $(k^*,\ell^*)$ PNE
  2. $k^* \in \arg\max_{k \in S_1}(\min_{\ell \in S_2} u_1(k,\ell))$ (maxmin), $\ell^* \in \arg\min_{\ell \in S_2}(\max_{k \in S_1} u_1(k,\ell))$ (minmax) and \[\max_{k \in S_1}(\min_{\ell \in S_2} u_1(k,\ell)) =\min_{\ell \in S_2}(\max_{k \in S_1} u_1(k,\ell)).\]
Rock-Paper-Sissors:

RPS
R(0,0)(-1,1)(1,-1)
P(1,-1)(0,0)(-1,1)
S(-1,1)(1,-1)(0,0)
Computational Game Theory (SoSe24), §1. Strategic Games
Lukas Graf (lukas.graf@uni-passau.de)